package cn.edu.xjtu.data_structure.experiment.ex4;

interface EdgeADT{
    public int v1();
    public int v2();
}

interface GraphADT {
    public int n();
    public int e();
    public Edge First(int v);
    public Edge next(Edge w);
    public boolean isEdge(Edge w);
    public boolean isEdge(int i, int j);
    public int v1(Edge w);
    public int v2(Edge w);
    public void setEdge(int i, int j, int weight);
    public void setEdge(Edge w, int weight);
    public void delEdge(Edge w);
    public void delEdge(int i,int j);
    public int weight(Edge w);
    public int weight(int i, int j);
    public void setMark(int v, int val);
    public int getMark(int v);
}

class Edge implements EdgeADT{

    private int vert1,vert2;

    public Edge(int vt1,int vt2){vert1 = vt1; vert2 = vt2;}

    @Override
    public int v1() {
        return vert1;
    }

    @Override
    public int v2() {
        return vert2;
    }
}

public class Graph implements GraphADT {

    private int[][]matrix;
    private int numEdge;
    private int[] Mark;

    public Graph(int n){
        Mark = new int[n];
        matrix = new int[n][n];
        numEdge = 0;
    }


    @Override
    public int n() {
        return Mark.length;
    }

    @Override
    public int e() {
        return numEdge;
    }

    @Override
    public Edge First(int v) {
        for (int i = 0; i<Mark.length; i++)
            if(matrix[v][i]!=0)
                return new Edge(v,i);
        return null;
    }

    @Override
    public Edge next(Edge w) {
        if(w == null)   return null;
        for (int i = w.v2() + 1; i < Mark.length; i++)
            if(matrix[w.v1()][i]!=0)
                return new Edge(w.v1(),i);
        return null;
    }

    @Override
    public boolean isEdge(Edge w) {
        if(w == null)   return false;
        else return matrix[w.v1()][w.v2()]!=0;
    }

    @Override
    public boolean isEdge(int i, int j) {
        return matrix[i][j]!=0;
    }

    @Override
    public int v1(Edge w) {
        return w.v1();
    }

    @Override
    public int v2(Edge w) {
        return w.v2();
    }

    @Override
    public void setEdge(int i, int j, int weight) {
        matrix[i][j]=weight;
        numEdge++;
    }

    @Override
    public void setEdge(Edge w, int weight) {
        setEdge(w.v1(),w.v2(),weight);
    }

    @Override
    public void delEdge(Edge w) {
        if(w!=null){
            if(matrix[w.v1()][w.v2()]!=0) {
                matrix[w.v1()][w.v2()] = 0;
                numEdge--;
            }
        }
    }

    @Override
    public void delEdge(int i, int j) {
        if(matrix[i][j]!=0) {
            matrix[i][j] = 0;
            numEdge--;
        }
    }

    @Override
    public int weight(Edge w) {
        return matrix[w.v1()][w.v2()];
    }

    @Override
    public int weight(int i, int j) {
        return matrix[i][j];
    }

    @Override
    public void setMark(int v, int val) {
        Mark[v] = val;
    }

    @Override
    public int getMark(int v) {
        return Mark[v];
    }
}


